package 中等.动态规划.矩阵路径;

/**
 * 在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值
 * （价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次
 * 向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上
 * 面的礼物的价值，请计算你最多能拿到多少价值的礼物？
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof
 */
public class 礼物的最大价值_offer47 {

    public static void main(String[] args) {

        礼物的最大价值_offer47 impl = new 礼物的最大价值_offer47();

        impl.maxValue(new int[][]{
                {1, 3, 1},
                {1, 5, 1},
                {4, 2, 1}
        });

    }

    private int maxSum = 0;

    private int[][] visited;

    /**
     * 回溯+记忆化+剪枝（超时）
     * 可以记录到达这个节点的最大礼物价值，如果多次从该节点出发
     * 查找，当前总和小于最大礼物价值的可以进行剪枝
     */
    public int maxValue(int[][] grid) {

        visited = new int[grid.length][grid[0].length];

        dfs(0, 0, 0, grid);

        return maxSum;
    }

    private void dfs(int i, int j, int sum, int[][] grid) {
        if (i == 1 && j == 1) {
            System.out.println();
        }
        sum += grid[i][j];

        if (i == grid.length - 1 && j == grid[0].length - 1) {
            maxSum = Math.max(maxSum, sum);
            return;
        }

        if (visited[i][j] > 0 && sum < visited[i][j]) {
            return;
        }
        visited[i][j] = Math.max(visited[i][j], sum);

        if (i + 1 < grid.length) {
            dfs(i + 1, j, sum, grid);
        }
        if (j + 1 < grid[0].length) {
            dfs(i, j + 1, sum, grid);
        }
    }

    /**
     * 动态规划
     * dp[i][j] 代表 到达 grid[i][j] 的最大价值总和
     * 状态转移方程
     * dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]) + grid[i][j]
     */
    public int maxValue2(int[][] grid) {
        int[][] dp = new int[grid.length][grid[0].length];

        dp[0][0] = grid[0][0];
        for (int i = 1; i < grid.length; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < grid[0].length; j++) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }

        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[dp.length - 1][dp[0].length - 1];
    }

}
